package 分类.数据结构设计;

import org.w3c.dom.Node;

import java.util.HashMap;

public class LRU {
    class Node{
        int key;
        int val;
        Node next;
        Node pre;
        public Node(){}
        public Node(int key,int val,Node next,Node pre){
            this.key=key;
            this.val=val;
            this.next=next;
            this.pre=pre;
        }
        public Node(int key,int val){
            this.key=key;
            this.val=val;
        }
    }
    HashMap<Integer, Node> hashMap=new HashMap<>();

    int capacity;
    int size=0;
    Node head=new Node();
    Node tail=new Node();
    public LRU(int capacity){
        this.capacity=capacity;
        head.next=tail;
        tail.pre=head;
    }

    int get(int key){
        if(hashMap.containsKey(key)){
            makeRecently(hashMap.get(key));
            return hashMap.get(key).val;
        }else {
            return -1;
        }
    }

    void put(int key,int val){
        Node node=hashMap.get(key);
        if(node==null){
            Node node1=new Node(key,val);
            hashMap.put(key,node1);
            addtoHead(node1);
            ++size;
            if(size>capacity){
                Node last=removeLast();
                hashMap.remove(last.key);
                --size;
            }
        }else {
            node.val=val;
            makeRecently(node);
        }
    }

    void makeRecently(Node node){

        remove(node);
        addtoHead(node);
    }
    void remove(Node node){
        node.pre.next=node.next;
        node.next.pre=node.pre;
    }
    void addtoHead(Node node){
        node.next=head.next;
        node.pre=head;
        head.next.pre=node;
        head.next=node;
    }

    Node removeLast(){
        Node last=tail.pre;
        remove(last);
        return last;
    }

}
